1. Field of the Invention
The present invention relates to an apparatus for providing random bit stream and, in particular, to an apparatus based on jittered oscillator sampling.
2. Description of Prior Art
Symmetric and asymmetric ciphering algorithms require an availability of a high quality random number source for key generation. Random numbers are also used for generating challenges in authentication protocols, to create padding bytes and blinding values for random masking.
Even if pseudo random number generators (PRNG; PRNG=pseudo random number generator) based on cryptographic secure deterministic algorithms can be employed for these purposes, a physical source of true randomness is needed for algorithm seeding. For this reason, a cryptographic token, like a chip-card, must also feature a true random number generator (RNG; RNG=random number generator) among its peripheral devices.
The main feature of a high-quality randomness source is the unpredictability of the produced bit stream. An observer or even attacker must not be able to carry out any useful prediction about the true RNG output even if the design of the RNG is known.
A true RNG generates a random bit stream from a non-deterministic natural source like an electronic noise or a radioactive decay. Indeed, in an integrated implementation, electronic noise sources like thermal or shot noise are the only stochastic processes that can be exploited.
According to the prior art, three different techniques for generating random bit streams can be considered: Direct amplification of a noise source, jittered oscillator sampling and discrete-time chaotic maps.
The first technique, a direct amplification of a noise source, exploits an amplification of a white noise source which is usually thermal noise from an integrated resistor or a shot noise from active devices. A high-gain amplifier is required to obtain a noise signal whose amplitude is large enough for further processing like a comparison to a voltage reference and sampling. The main issue when designing an amplification-based RNG is an offset voltage after the noise amplifier. An offset much smaller than a noise standard deviation is needed in order to obtain a good quality random bit stream. A noise amplifier bandwidth is also an issue if a fast sampling frequency is required. A further drawback is the presence of an internal disturbance from a power supply, a substrate or a cross-coupling, and an external disturbance whose power level can be higher than the random noise level at the amplifier input, if proper design techniques are not employed. As a consequence, periodic patterns can be forced in the true RNG's output, thus affecting its statistical quality and unpredictability. Periodic patterns are a main concern in a chip-card implementation of a RNG, since no adequate external shielding is usable and the RNG is integrated on a common silicon substrate close to noisy digital circuits. To address the offset problem, in W. T. Holman, J. A. Connelly, and A. B. Downlatabadi, “An integrated analog/digital random noise source”, IEEE Trans. Circuits and Syst. I, vol. 44, no 6. pp. 521-528, June 1997 a simple low-pass filter is used to cancel the offset voltage at the amplifier output. The proposed solution requires a chip area which is too large and, moreover, the comparator offset is not removed sufficiently. In M. Bucci, L. Germani, R. Luzzi, P. Tommasino, A. Trifiletti, M. Varanonuovo, “A high speed truly IC random number source for Smart Card microcontrollers”, Proc. 9th IEEE International Conf. on Electronics, Circuits and Systems (ICECS 2002), pp. 239-242, Sept. 2002 and M. Bucci, L. Germani, R. Luzzi, P. Tommasino, A. Trifiletti, M. Varanonuovo, “A high speed IC random number source for Smart Card microcontrollers”, IEEE Trans. Circuits and Syst. I, vol. 50, no. 11, pp. 1377-1380, Nov 2003, an amplification-based true RNG is reported which features a precise offset zeroing system without employing external components and large capacitors.
A true RNG based on the second technique, the jittered oscillator sampling, basically, includes two free running oscillators and a sampling element like a single D-type flip-flop. An output signal from a slower of the two oscillators samples an output of the faster of the two oscillators, thus generating a bit stream. The resulting bit sequence derives from the oscillators mean frequency ratio and their cycle-to-cycle jitter. Properly chosen frequency ratios lead to bit streams that seem to be more random when statistical randomness tests are applied. Nevertheless, the output bit entropy is due to the oscillator's jitter being the only randomness source in such a system. If the sample signal of the fast oscillator features an unbalanced mean value, this in turn gives rise to an unbalanced mean value on the output bit stream or to an increase in its bit-to-bit correlation, according to the adopted sampling element. Anyway, this is not the main disadvantage to consider. Moreover, periodic disturbances like a system clock can synchronize the sampling oscillator, thus dramatically reducing its jitter. In M. Bucci, L. Germani, R. Luzzi, A. Trifiletti, M. Varanonuovo, “A high-speed oscillator-based truly random number source for Cryptographic Applications on a Smart Card IC”, IEEE Trans. Computers, vol. 52, no. 4, pp. 403-490, April 2003 an oscillator-based true RNG is reported where the sampling oscillator features an amplified noise source inside, thus obtaining a very high jitter-to-mean period ratio of about 10%. This increases the random bit stream quality, at the expense of an increase in area and power requirements.
FIG. 1 shows a schematic view of a jittered oscillator sampling based RNG according to the prior art. An RNG source 100 comprises a high-frequency oscillator 102, a low-frequency oscillator 104, a prescaler 106 and a sampler 108. The sampler 108 is a D-flip-flop. The high-frequency oscillator 102 generates a fast clock signal 110 which is a data input to the sampler 108. The low-frequency oscillator 104 generates a slow clock signal 112 which is prescaled by the prescaler 106. The prescaler 106 outputs a sample signal 114 which is an input to a clock input of the sampler 108. The sampler 108 samples the fast clock signal 110 on a rising edge of the sample signal 114 and outputs a random bit 116 which depends on a sampling state of the fast clock signal 110 while being sampled. Here, successive random bits 116 are an input to a digital post-processor 120 which outputs a random bit stream 122.
FIG. 2 shows characteristics of the fast clock signal 110, the slow clock signal 112 and the sample signal 114, as they are shown in FIG. 1. The fast clock signal 110 has a period TFAST and a duty cycle d. The slow clock signal 112 has a period TSLOW. Edges of the slow clock signal 112 comprise a jitter. The sample signal 114 is generated from the slow clock signal 112 by prescaling the sample signal 112 by a factor defined in the prescaler. Here the slow clock signal 112 is prescaled by a factor of 4. As the sample signal 114 is generated from the slow clock signal 112, the edge of the sample signal 114 comprises a jitter, too. A period of the sample signal 114 is TSAMPLE and a standard deviation of the jitter of the sample signal 114 is σ(TSAMPLE). Edges of the sample signal 114 and the fast clock signal 110 are not synchronized. Here the edge of the fast clock signal 110 occurs by a time period t0 later than the edge of the sample signal 114. Frequency beating of the two free running oscillators 102, 104 (shown in FIG. 1) generates a non-white noise signal. This is especially a problem in a standard-cell based RNG where typically the jitter has a low intensity. Moreover, an unbalanced random bit stream 122 is obtained if the duty cycle d of the fast clock signal 110 is unbalanced. A relative jitter with respect to the fast clock signal is helpful.
The last cited technique, based on discrete-time chaotic maps exploits a sampling of a chaotic system to generate a random bit sequence. Non-linear or piece-wise linear systems can show a chaotic behavior under proper conditions for their internal parameters. Under chaotic conditions, two arbitrary close initial states lead to two completely different system evolutions. Therefore, the sources of randomness are the error or noise over the measurement of the initial state and the noise contribution during the state transitions. Unfortunately, when implementing a chaotic system in a physical device, environmental and process variations cause parameter variations that can force the system to leave its chaotic behavior thus evolving according to a periodic trajectory. Reference for chaotic-based true RNGs are in T. Stojanovski and L. Kocarev, “Chaos-based random number generators—Part I: Analysis”, IEEE Trans. Circuits and Syst. I, vol. 48, no. 3, pp. 281-288, March 2001 and T. Stojanovski, J. Pihl, and L. Kocarev, “Chaos-based random number generators—Part II: Practical realization”, IEEE Trans. Circuits and Syst. I, vol. 48, no. 3, pp. 382-385, March 2001.
Since different techniques feature different advantages, to increase the quality of the overall source, in C. S. Petrie, J. A. Connelly, “A noise-based IC random number generator for applications in cryptography”, IEEE Trans. Circuits and Systems I, vol. 47, no. 5, pp. 615-621, May 2000 a true RNG which adopts a mixing of the three above mentioned RNG techniques is presented. A source quite resistant to deterministic disturbances is achieved even if, due to the mixing of different techniques, it is difficult to provide a statistical model for the system that allows to certify its operation. A more effective solution, a post-processing of the whole bit stream from the source with a carefully designed correcting or decorrelating algorithm, that features some compression too, can be employed. A lower speed bit stream with increased statistical quality is generated from a high-speed near-random input stream by selecting its entropy portions.
From the above, it follows, that every random source, even if well-designed, generates a bit stream that usually shows a certain level of correlation, among other, due to bandwidth limitation, fabrication tolerances, aging and temperature drifts or deterministic disturbances.